package cc.wx.fom.ds;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 创建于:2015年7月8日<br>
 * 无向图的实现
 * 
 * @author WangXue
 * @version 1.0.0
 */
public class UndirectedGraph implements IUndirectedGraph {
	private Map<String, IVertex> vertexMap = new HashMap<String, IVertex>();
	// private List<IVertex> vertexs = new ArrayList<IVertex>();
	private List<IEdge> edges = new ArrayList<IEdge>();

	private Map<IVertex, IVertex> parentVertex = new HashMap<IVertex, IVertex>();
	/**
	 * 已经走过的顶点
	 */
	private List<IVertex> routedVertexs = new ArrayList<IVertex>();

	@Override
	public String toString() {
		String v = vertexMap.values().toString();
		String e = edges.toString();
		return v + "\r\n" + e;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see cc.wx.fom.ds.IUndirectedGraph#getVexNum()
	 */
	@Override
	public int getVexNum() {
		return vertexMap.size();
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see cc.wx.fom.ds.IUndirectedGraph#getEdgeNum()
	 */
	@Override
	public int getEdgeNum() {
		return edges.size();
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see cc.wx.fom.ds.IUndirectedGraph#getVertex()
	 */
	public Collection<IVertex> getVertex() {
		return vertexMap.values();
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see cc.wx.fom.ds.IUndirectedGraph#getEdge()
	 */
	@Override
	public Collection<IEdge> getEdge() {
		return edges;
	}

	@Override
	public IVertex insertVertex(String vid) {
		if (vertexMap.containsKey(vid)) {
			throw new RuntimeException("该顶点已存在:" + vid);
		}
		IVertex vertex = new Vertex(vid);
		vertexMap.put(vid, vertex);
		return vertex;
	}

	public void removeVertex(String vid) {
		IVertex vertex = vertexMap.get(vid);
		if (vertex == null) {
			throw new RuntimeException("该顶点不存在");
		}
		List<IEdge> es = vertex.getEdges();
		List<IVertex> vs = vertex.getNearVertexs();
		// TODO 这样不严谨，以后再改进
		for (IEdge e : es) {
			for (IVertex v : vs) {
				v.removeEdge(e);
			}
		}
		vertexMap.remove(vid);
	}

	@Override
	public boolean containsVertex(String vid) {
		return vertexMap.containsKey(vid);
	}

	@Override
	public void insertEdge(String vid1, String vid2) {
		IVertex v1 = vertexMap.get(vid1);
		IVertex v2 = vertexMap.get(vid2);
		if (v1 == null || v2 == null) {
			throw new RuntimeException("未包含两顶点之一，无法插入边:" + vid1 + "," + vid2);
		}
		IEdge edge = new Edge(v1, v2);
		if (edges.contains(edge)) {
			throw new RuntimeException("已包含该边");
		} else {
			edges.add(edge);
		}
		v1.addEdge(edge);
		edge = new Edge(v2, v1);
		v2.addEdge(edge);
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see cc.wx.fom.ds.IUndirectedGraph#areAdjacent(cc.wx.fom.ds.IVertex,
	 * cc.wx.fom.ds.IVertex)
	 */
	@Override
	public boolean areAdjacent(IVertex u, IVertex v) {
		if (!vertexMap.containsValue(u) || !vertexMap.containsValue(v)) {
			throw new RuntimeException("图中不存在顶点");
		}
		for (IEdge edge : edges) {
			if (edge.areAdjacent(u, v)) {
				return true;
			}
			if (edge.areAdjacent(v, u)) {
				return true;
			}
		}
		return false;
	}

	// /*
	// * (non-Javadoc)
	// *
	// * @see cc.wx.fom.ds.IUndirectedGraph#edgeFromTo(cc.wx.fom.ds.IVertex,
	// * cc.wx.fom.ds.IVertex)
	// */
	// @Override
	// public IEdge edgeFromTo(IVertex u, IVertex v) {
	// if (!vertexs.contains(u) || !vertexs.contains(v)) {
	// throw new RuntimeException("图中不存在该顶点");
	// }
	// List<IEdge> edges = u.getEdges();
	// for (IEdge edge : edges) {
	// if (edge.endWith(v)) {
	// return edge;
	// }
	// }
	// return null;
	// }

	/*
	 * (non-Javadoc)
	 * 
	 * @see cc.wx.fom.ds.IUndirectedGraph#adjVertexs(cc.wx.fom.ds.IVertex)
	 */
	@Override
	public List<IVertex> adjVertexs(IVertex u) {
		List<IEdge> edges = u.getEdges();
		List<IVertex> vertexs = new ArrayList<IVertex>();
		for (IEdge edge : edges) {
			IVertex v = edge.getHeadVertex();
			if (v == u) {
				v = edge.getTailVertex();
			}
			vertexs.add(v);
		}
		return vertexs;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see cc.wx.fom.ds.IUndirectedGraph#DFSTraverse(cc.wx.fom.ds.IVertex)
	 */
	@Override
	public List<IVertex> DFSTraverse(IVertex v) {
		return null;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see cc.wx.fom.ds.IUndirectedGraph#BFSTraverse(cc.wx.fom.ds.IVertex)
	 */
	@Override
	public List<IVertex> BFSTraverse(IVertex v) {
		// TODO Auto-generated method stub
		return null;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see cc.wx.fom.ds.IUndirectedGraph#shortestPath(cc.wx.fom.ds.IVertex)
	 */
	@Override
	public List<IEdge> shortestPath(IVertex v) {
		return null;
	}

	@Override
	public List<IVertex> shortestPath(IVertex start, IVertex end) {
		routedVertexs = new ArrayList<IVertex>();
		parentVertex = new HashMap<IVertex, IVertex>();
		routedVertexs.add(start);
		start = vertexMap.get(start.getId());
		if (start == null) {
			throw new RuntimeException("开始节点不存在");
		}
		end = vertexMap.get(end.getId());
		if (end == null) {
			throw new RuntimeException("结束节点不存在");
		}
		List<IVertex> results = new ArrayList<IVertex>();
		List<IVertex> nearVertexs = start.getNearVertexs();
		if (nearVertexs != null && nearVertexs.size() > 0) {
			for (IVertex v : nearVertexs) {
				if (!parentVertex.containsKey(v)) {
					parentVertex.put(v, start);
				}
				routedVertexs.add(v);
			}
		}
		while (nearVertexs != null && nearVertexs.size() > 0) {
			if (nearVertexs.contains(end)) {
				results.add(end);
				IVertex parent = parentVertex.get(end);
				results.add(parent);
				while (!parent.equals(start)) {
					parent = parentVertex.get(parent);
					results.add(parent);
				}
				break;
			}
			routedVertexs.addAll(nearVertexs);
			nearVertexs = getChild(nearVertexs);
		}

		// 反转结果
		List<IVertex> newResult = new ArrayList<IVertex>();
		for (int i = results.size(); i > 0; i--) {
			IVertex v = results.get(i - 1);
			newResult.add(v);
		}
		return newResult;
	}

	private List<IVertex> getChild(List<IVertex> vertexs) {
		List<IVertex> result = new ArrayList<IVertex>();
		for (IVertex vertex : vertexs) {
			List<IVertex> vs = vertex.getNearVertexs();
			if (vs != null) {
				for (IVertex v : vs) {
					if (!result.contains(v) && !routedVertexs.contains(v)) {
						result.add(v);
						parentVertex.put(v, vertex);
					}
				}
			}
		}
		return result;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see cc.wx.fom.ds.IUndirectedGraph#generateMST()
	 */
	@Override
	public void generateMST() {
		// TODO Auto-generated method stub

	}

}
